1. Technical Field
This invention relates to allocation of space in persistent storage. More specifically, the invention relates to efficiently allocating blocks of persistent storage while concurrently mitigating contention among multiple threads.
2. Description of the Prior Art
File systems and databases are comprised of a plurality of files, with each individual file using disk space from persistent storage. In certain implementations, a block serves as a basic unit of space allocation in a file system and database. When a new file is created or an existing file is extended, it will require new or additional blocks of disk space within persistent storage. Similarly, when a new database is created or an existing database is extended, it will require new or additional blocks within persistent storage. A free space bit map (FSBM) is used to track blocks of space from persistent storage which are available for allocation to a file. The FSBM is a part of the file system metadata or database metadata. The FSBM is stored in persistent storage and is typically divided into pages. The FSBM is comprised of a string of bits, wherein each bit represents one block of disk space from persistent storage. When the file system or database is initially created, all bits in the FSBM are available. As files are created and written, the associated block becomes unavailable and this is recorded in the FSBM. Similarly, when files or databases are truncated or deleted, bits in the FSBM may once again become available.
FIG. 1 is a block diagram (30) of a sample free space bit map. In this example there are seven entries (32), (34), (36), (38), (40), (42), and (44), with each entry corresponding to blocks of disk space in associated persistent storage. Each entry in the free space bit map has a bit, and the value of the bit denotes whether the corresponding block of disk space in persistent storage is currently in use. In one embodiment, the value of zero is representative of availability of corresponding disk space, and a value of one is representative of unavailability of corresponding disk space. As shown in FIG. 2, the first entry (32), the second entry (34), the third entry (36), and the fifth entry (40) are all represented by a bit value of one indicating each of the corresponding blocks of disk space in persistent storage are currently in use and unavailable to a file or database. The fourth entry (38), the sixth entry (42), and the seventh entry (44), are all represented by a bit value of zero indicating that the corresponding blocks of disk space in persistent storage are not in use and are available for allocation to a file or database.
In the prior art, a request for persistent storage space will institute a search of the FSBM starting from an ending position of a prior search of the FSBM. Routines for allocating blocks of disk space from the persistent storage require a linear search of the FSBM for a series of consecutive bits that will fulfill the disk space required for the allocation. The size of the FSBM corresponds to the size of the persistent storage space, i.e. a large storage system will have a large FSBM. Therefore, a linear search of the FSBM is inefficient due to the size of the FSBM, and the fact that it is not part of the computer's random access memory. In addition, in a computer system supporting multiple processes, it is foreseeable that several threads may try to perform an allocation of persistent storage space at the same time. Prior art routines serialize access of threads to pages of the FSBM. However, serialized access of the FSBM does not allow multiple threads to access pages of the FSBM simultaneously. Accordingly, there are limitations associated with prior art management and allocation of persistent storage space.
Therefore, there is a need for efficiently coordinating access to persistent storage that eliminates the need to conduct a linear search of the FSBM to determine availability of consecutive bits in accordance with size requirements of a space request. In addition, there is a need for accommodating access to the FSBM by multiple processing threads.